The present invention relates to a method and to a device for removing error patterns in binary data, in particular for use in product coding.
For example, Solid State Storage (SSS) applications make use of Forward Error Correction (FEC) coding techniques for detecting and correcting errors in binary data in unreliable or noisy environments. FEC encoding adds redundancy to the binary data, so that between any two valid code words of the resulting code a minimum distance (Hamming distance) Dmin is ensured. In case of an FEC code with Dmin=2n+1, the decoding of such an encoded code word reveals up to Dmin−1=2n errors and may correct up to └(Dmin−1)/2┘=n errors. Such a code is therefore called an n-error correcting code.
The error detection and correction capability of the above-mentioned FEC coding techniques can be improved by also applying FEC across binary data words. To this end, multiple binary data words are organized in a two-dimensional data array with columns and rows, and FEC is applied per row and per column, respectively. Such coding schemes, also known as Product Code (PC) schemes, involve one or more decoding iterations applied to the binary data to be decoded, and each PC decoding iteration in turn involves FEC-based decoding of each of the rows and of each of the columns of the data array. PC coding schemes are of low complexity, and hence offer cost-efficient hardware implementation, high throughput and low latency. Moreover, they are well-suited for operation on large data arrays.
Using PC decoding schemes, errors which cannot be detected and/or corrected per code word may potentially be detected and/or corrected across code words. Applying an FEC technique across binary data words can also be understood as an interleaving scheme which eliminates error patterns that otherwise cannot be approached (e.g., burst errors), and thus lowers the error floor of FEC coding.
Even a PC decoding scheme may, however, arrive at error patterns whose errors can be detected but not be located exactly. Such error patterns cannot be eliminated any further, and are thus called pathologic error patterns. They arise due to the above-mentioned discrepancy between the error detecting and correcting capabilities of FEC codes. If a PC decoding scheme employs an n-error correcting FEC code, then a pathologic error pattern comprises at least n+1 positions in both the rows and the columns, i.e., a structure of minimum size (n+1)×(n+1), in which the errored rows and/or columns are not necessarily adjacent to each other. If different error correcting codes are chosen for rows and columns, also asymmetric structures may be conceivable, e.g., (m+1)×(n+1) where m≠n. Besides FEC-detected errors, also invisible errors, which arise by spurious FEC corrections, may contribute to a pathologic error pattern. Despite the probability of an (n+1)×(n+1) pathologic error pattern being quite low, it may nevertheless be quite significant for SSS applications. In particular, he focus is on pathologic error patterns of minimum size, because those of larger size, e.g., up to (2n+1)×(2n+1), have a significantly lower probability to appear.
In US 2014/0201604 A1, methods and systems for 2-dimensional Forward Error Correction coding are disclosed. The communication system includes an encoder configured to encode source data and output an encoded frame including a plurality of rows and a plurality of columns. The plurality of rows includes a row component code. The plurality of columns includes a column component code. The row component code is configured to achieve a lower bit error rate than the column component code in communication channels having a same signal to noise ratio.
U.S. Pat. No. 8,656,245 B2 proposes a method of error floor mitigation in low-density parity-check codes. The decoding method decodes the low-density parity-check coded messages within a bipartite graph having check nodes and variable nodes. Messages from check nodes are partially hard limited, so that every message which would otherwise have a magnitude at or above a certain level is re-assigned to a maximum magnitude.
In U.S. Pat. No. 8,677,227 B2, a method and a system for decoding are disclosed. Low-Density Parity-Check (LDPC) codes offer error correction at rates approaching the link channel capacity and reliable and efficient information transfer over bandwidth or return-channel constrained links with data-corrupting noise present. They also offer performance approaching channel capacity exponentially fast in terms of the code length, linear processing complexity, and parallelism that scales with code length. They also offer challenges relating to decoding complexity and error floors limiting achievable bit-error rates. Accordingly encoders with reduced complexity, reduced power consumption and improved performance are disclosed with various improvements including simplifying communications linking multiple processing nodes by passing messages where pulse widths are modulated with the corresponding message magnitude, delaying a check operation in dependence upon variable node states, running the decoder multiple times with different random number generator seeds for a constant channel value set, and employing a second decoder with a randomizing component when the attempt with the first decoder fails.
U.S. Pat. No. 8,595,590 B1 discloses systems and methods for encoding and decoding check-irregular non-systematic Irregular Repeat-Accumulate (IRA) codes of messages in any communication or electronic system where capacity achieving coding is desired. According to these systems and methods, IRA coding strategies, including ones that employ capacity-approaching non-systematic IRA codes that are irregular and that exhibit a low error floor, are employed. These non-systematic IRA codes are particularly advantageous in scenarios in which up to half of coded bits could be lost due to channel impairments and/or where complementary coded bits are desired to transmit over two or more communications sub-channels. An encoder includes information bit repeaters and encoders, one or more interleavers, check node combiners, a check node by-pass and an accumulator. A decoder includes a demapper, one or more check node processors, an accumulator decoder, a bit decoder, and one or more interleavers/deinterleavers.
In U.S. Pat. No. 8,484,535 B2, error-floor mitigation of codes using write verification is disclosed. Executed when a channel input (e.g., LDPC) codeword is written to a storage medium, a write-verification method compares the channel input codeword to the written codeword, identifies any erroneous bits, and stores the erroneous-bit indices to a record in a table. At some later time, the written codeword is read and sent to a decoder. If the decoder fails with a near codeword, a write-error recovery process searches the table and retrieves the erroneous-bit information. The codeword bits at those indices are adjusted, and the modified codeword is submitted to further processing.
U.S. Pat. No. 8,255,763 B1 proposes an error correction system using an iterative product code. Such an error correction system includes an iterative code that employs an interleaved component code and an embedded parity component code. On the transmission side, input signals received at an input node are encoded based on the interleaved code, which encodes an interleaved version of the input data to produce a first set of codewords. A portion of the first set of codewords is divided into a plurality of symbols which are encoded based on the embedded parity code. On the receiving side, received data are detected to produce detected information and soft outputs. The detected information is decoded based on the embedded parity code to obtain decoded information. The decoded information is used with other soft information by an interleaved decoder to generate reliability metrics for biasing a subsequent decoding iteration.
Accordingly, it is an aspect of the present invention to improve removing pathologic error patterns in binary data, in particular in product coding schemes.